/*********************************************************************************
 * Software License Agreement (BSD License)
 * Copyright (c) 2012, Carlos D. Correa (info@ngraph.org)
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. Neither the name of netzen nor the
 *    names of its contributors may be used to endorse or promote products
 *    derived from this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL <COPYRIGHT HOLDER> BE LIABLE FOR ANY
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
 *  LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *********************************************************************************/
#include "mst.h"

#include "timing.h"
#include "node.h"
#include <set>
#include <assert.h>
#include <algorithm>
#include <queue>

struct min_edge_comp {
  bool operator() (EdgeInfo* e1, EdgeInfo* e2) { return e1->weight < e2->weight; }
};

struct max_edge_comp {
  bool operator() (EdgeInfo* e1, EdgeInfo* e2) { return e1->weight > e2->weight; }
};

MST::MST(string name, Controller *controller):AnalysisTool("Graph",name.c_str(),controller) {
}

int MST::addSet(int id) {
  Set s;
  s.push_back(id);
  int n = sets.size();
  sets.push_back(s);
  return n;
} 
int MST::getSet(int n) {
  int curset;
  if(reps.find(n)==reps.end()) {
    //printf("Set for node %d does not exist\n", n);
    curset = addSet(n);
    reps[n] = curset;
  } else {
    //printf("Set for node %d is %d\n", n, reps[n]);
    curset = reps[n];
  }
  return curset;
}
void MST::mergeSets(int i, int j) {
  //printf("Merging sets %d %d\n", i, j);
  for(unsigned int k=0;k<sets[j].size();k++) {
    int n = sets[j][k];
    sets[i].push_back(n);
    reps[n] = i;
    //printf("Adding node %d to set %d\n", n, i);
  }
  sets[j].clear();
}

void MST::compute() {
  assert(controller);
  // TO DO: set up these two via UI
  string resultProp = getPropertyString("Result");
  string weight = PROPERTY(getPropertyString("Weight"));
  bool minimumTree = getPropertyBool("Minimum");
  Graph *graph = controller->getGraph("graph");

  controller->addDataProperty("edge", resultProp, PROPERTY_BOOL);


  sets.clear();
  reps.clear();
  MSTlist.clear();
  vector<EdgeInfo *> edges;
  edges.clear();
  if(listener) listener->setProgress(0);

	ElementIterator *it = graph->createEdgeIterator();
	for(it->begin();it->hasMoreElements();) {
		Edge *edge = (Edge*) it->next();
		int i = edge->getNode0()->getIndex();
		if(listener) listener->setProgress((float) i/(float) graph->numNodes());
		assert(edge);
		assert(edge->getNode1());
		int j = edge->getNode1()->getIndex();
		float d = graph->getAsFloat(edge,weight);
		EdgeInfo *e = new EdgeInfo;
		e->i = i;
		e->j = j;
		e->weight = (d);
		edges.push_back(e);
    }
  
	graph->destroyIterator(it);
	
  if(minimumTree) {
    sort(edges.begin(), edges.end(), min_edge_comp());
  } else {
    sort(edges.begin(), edges.end(), max_edge_comp());
  }

  MSTlist.clear();

  for(unsigned int k =0;k<edges.size();k++) {
    int i = edges[k]->i;
    int j = edges[k]->j;
    int setI = getSet(i);
    int setJ = getSet(j);
    if(setI!=setJ) {
      MSTlist.push_back(edges[k]);
      if(setI!=setJ) mergeSets(setI, setJ);
    }
  }

	
	it = graph->createEdgeIterator();
	for(it->begin();it->hasMoreElements();) {
		Edge *edge = (Edge*) it->next();
		edge->setPropertyBool(resultProp, false);
      //edge->setPropertyFloat(resultProp, 0.0);
	}
	graph->destroyIterator(it);
	
  string nodeProperty = getPropertyString("Node Weight");
  float maxValue = -0.1;
  int root = -1;

 	it = graph->createNodeIterator();
	for(it->begin();it->hasMoreElements();) {
		Node *node = (Node*) it->next();
		int i = node->getIndex();

		node->setPropertyInt("Parent", -1);
		float v = graph->getAsFloat(node,nodeProperty);
		if(v>maxValue) {
		  maxValue = v;
		  root = i;
		}
	}
	graph->destroyIterator(it);

  int n = (int) graph->numNodes();
  bool *mst = new bool[n*n];
  for(int i=0;i<n*n;i++) mst[i] = false;

  for(unsigned int k =0;k<MSTlist.size();k++) {
    int i = MSTlist[k]->i;
    int j = MSTlist[k]->j;
    assert(graph->getNode(i));
    assert(graph->getNode(j));
    graph->getEdge(i,j)->setPropertyBool(resultProp, true);
    mst[n*i+j] = mst[n*j+i] = true;
  }

  queue<int> bfs;
  bfs.push(root);

  bool *visited = new bool[(int) graph->numNodes()];
  for(unsigned int i=0;i<graph->numNodes();i++) {
    visited[i] = false;
  }
  while(!bfs.empty()) {
    int i = bfs.front();
    visited[i] = true;
    bfs.pop();
		NodeIterator *it = graph->getNeighbors(i);
		for(it->begin();it->hasMoreElements();) {
			Node *node = (Node*) it->next();
      int idx = node->getIndex();
      bool inMst = mst[n*i+idx]; 
      if(inMst) {
				if(!visited[idx]) {
					node->setPropertyInt("Parent", i);
					bfs.push(idx);
				}
      }
    }
		graph->destroyIterator(it);
  }
  delete visited;
  delete mst;

    //graph->computeEdgeMinMaxFloat(resultProp);
  graph->computeEdgeMinMaxBool(resultProp); // 0612 yuhsuan

  controller->addDataProperty("node", "Parent", PROPERTY_INT);
  if(listener) listener->done();

}

Skeleton::Skeleton(string name, Controller *controller): MST(name.c_str(),controller)  {
}

void Skeleton::compute() {
	assert(controller);
	string resultProp = getPropertyString("Result");
	Graph *graph = controller->getGraph("graph");
	assert(graph);
	
	MST::compute();
	// Add Skeleton Edges
	string edgeProp = getPropertyString("Skeleton Property");
	EdgeIterator* it = graph->createEdgeIterator();
	for(it->begin();it->hasMoreElements();) {
		Edge *edge = (Edge*) it->next();
		assert(edge);
		bool inSkeleton = graph->getAsBoolean(edge, edgeProp);
		if(inSkeleton) {
			edge->setPropertyBool(resultProp, true);
		}
	}
	graph->destroyIterator(it);
	// Delete MSTlist and edges
	
}

AnalysisTool* createMSTTool(Controller *controller) {
  AnalysisTool *t = new MST("Spanning Tree", controller);
  t->setPropertyStringList("Weight", "Default", "edge");
  t->setPropertyStringList("Node Weight", "Default", "node");
  t->setPropertyString("Result", "inMST");
  t->setPropertyBool("Minimum", true);
  return t;
}

AnalysisTool* createSkeletonTool(Controller *controller) {
	AnalysisTool *t = new Skeleton("Skeleton", controller);
	t->setPropertyStringList("Weight", "Default", "edge");
	t->setPropertyStringList("Node Weight", "Default", "node");
	t->setPropertyString("Result", "inSkeleton");
	t->setPropertyStringList("Skeleton Property", "Default", "edge");
	t->setPropertyBool("Minimum", true);
	return t;
}


